1. Field of the Invention
This invention relates to finding lines through axial objects and, more particularly, to finding a line that passes through a set of axial boxes in three-space and higher dimensions.
2. Description of the Related Art
Determining a line passing through a set of axial objects is a problem that has wide application. In the three-dimensional case, for example, the problem is especially important in computer graphics, when it is desirable to find a line-of-sight through a set of rectangular boxes or windows in the course of creating video displays. It is quite common to use sets of boxes in the digital computer representation of objects, such as computer axial tomographic (CAT) x-ray systems and nuclear magnetic resonance imaging (MRI) systems. See, for example, U.S. Pat. No. 4,710,876 to Cline et al. The general, n-dimensional case of the, problem is encountered in statistics, when it is desirable to find a linear approximation for an n-dimensional data set specified by a set of ranges along each dimension. A line passing through all axial objects in a set is said to be a transversal line.
An example of a three-dimensional axial box is illustrated in FIG. 1, in which a box: 10 is shown in three-space relative to three coordinate axes D.sub.1, D.sub.2, and D.sub.3. The six sides of the box are defined by eight vertices. The box is axial because each pair of adjacent vertices; defines a line segment that is parallel to one of the axes. Each vertex can be defined by a three-tuple (n.sub.1, n.sub.2, n.sub.3) in which the first position of the three-tuple is represented by either a.sub.i or b.sub.i where i=1, 2, 3. The value a.sub.1, corresponds to the minimum value of the box side along the D.sub.1 axis and the value b.sub.1 corresponds to the maximum value of the box side along the D.sub.1 axis. Similarly, the value a.sub.2 corresponds to the minimum value of the box side along the D.sub.2 axis and the value b.sub.2 corresponds to the maximum value of the box side along the D.sub.2 axis and, finally, a.sub.3 corresponds to the minimum value along D.sub.3 and b.sub.3 corresponds to the maximum value along D.sub.3. The projection of the box 10 onto the D.sub.1 -D.sub.3 axial plane is shown in FIG. 1 to better illustrate the values of a.sub.1, a.sub.3, b.sub.1, and b.sub.3 along the respective D.sub.1 and D.sub.3 axes. The projection of the box onto the other axial planes should be apparent.
An example of the problem of finding a line passing through a plurality of three-dimensional axial boxes is shown in FIG. 2, in which three boxes 20, 22, and 24 are shown relative to three coordinate axes D.sub.1, D.sub.2, and D.sub.3 with a line 26 passing through all three boxes. The transversal line 26 is defined by two points X and Y. The point X is specified by the three-tuple (x.sub.1, x.sub.2, x.sub.3), where the coordinates refer to the axes D.sub.1, D.sub.2, and D.sub.3, respectively. The point Y is specified by the three-tuple (y.sub.1, y.sub.2, y.sub.3). The line 26 happens to be parallel to the D.sub.1 axis but it should be clear that other lines not parallel to any of the coordinate axes also could pass through all three boxes 20, 22, and 24.
Those skilled in the art will recognize that the transversal line 26 extends through the three-dimensional space and that the line can be represented parametrically by u+tv, where u is a point on the line 26, v is a direction vector, and t is a scalar parameter. The scalar parameter t can be thought of as representing time and the point u=(u.sub.1, u.sub.2, u.sub.3) can be thought of as a point in the three-space defined by coordinate axes R.sub.1, R.sub.2, and R.sub.3, with v being a vector in the three-space.
Conventionally, the problem of finding a line that passes through a set of boxes as depicted in FIG. 2 can be determined by "brute force" enumeration in which attempts are made to fit a line segment through all of the boxes by a trial and error procedure, after which a parametric line representation is found. A digital computer can be programmed to begin at a first endpoint of a trial line segment and "draw" extensions outwardly in three-space to a second endpoint, creating a line segment. The extensions are tested for passing through all the boxes. Such procedures are cumbersome and inefficient for the three-dimensional case, at best, and quickly become extremely difficult when more than a few boxes are involved Brute force enumeration becomes virtually impossible in the general multi-dimensional case.
More sophisticated line-fitting methods have been developed, but these can be quite complex mathematically and difficult computationally. Often, such methods are not linear in terms of expected time to reach a solution in that doubling the number of boxes, for example, results in more than doubling the time to find a solution. Thus, the time to find a solution can increase dramatically when the number of boxes is increased or the dimensional space is enlarged. Even methods that provide solutions in linear expected time, that is, in what is referred to as O(n) time, can be quite complex mathematically and can involve, for example, probabilistic methods. See, for example, the article "Finding a Line Transversal of Axial Objects in Three Dimensions" by Nina Amenta in the Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, at pages 66-71 (1992).
From the discussion above, it should be apparent that there is a need for a method and apparatus that determines a line passing through axial boxes in three-space in linear time without requiring solution of complex equations and difficult computation. The present invention satisfies this need.